\section{动态规划}
\subsection{钢材的最大价格}
在开始讲解动态规划时我们先看一个这样的问题，现在有一根长度为 n 的钢材，不同长度的钢材价格不一样，价格列表如下\tabref{tab:steel_price}：
\begin{table}[!htbp]
	\centering
	\caption{钢材长度与价格}
	\begin{tabular}{ccccccccccc}
		\toprule
		长度   & 1 & 2 & 3 & 4 & 5  & 6  & 7  & 8  & 9  & 10 \\
		\midrule
		价格 p & 1 & 5 & 8 & 9 & 10 & 17 & 17 & 20 & 24 & 30 \\
		\bottomrule
	\end{tabular}
	\label{tab:steel_price}
\end{table}
现在给你一个长度为 n 的钢材，请问如何切割能保证钢材卖出的价格最高？我们可以分析一下，给定比较小的长度为 n 的钢材切割后的最大售价。
\begin{table}[H]
	\centering
	\caption{钢材长度与价格}
	\begin{tabular}{ccccccccccc}
		\toprule
		长度              & 1 & 2 & 3 & 4  & 5  & 6  & 7  & 8  & 9  & 10 \\
		\midrule
		最大切分价格 maxPrice & 1 & 5 & 8 & 10 & 13 & 17 & 18 & 22 & 25 & 30 \\
		\bottomrule
	\end{tabular}
	\label{tab:steel_total_price}
\end{table}
如\tabref{tab:steel_total_price} ，长度为5的钢材，我们可以选择将其切分为1+4、2+3或者不切分，分别对应的价格为10、13、10。所以可以得到长度为5的最大价格为13。另maxPrice(n)表示长度为n的钢材切分能获得的最大价格。则$maxPrice(n) = max(p[1]+p[n-1],p[2]+p[n-2],\ldots p[n-1,1])$，这里实际上不需要计算 n-1 次，因为$p[1]+p[n-1] = p[n-1]+p[1]$，代码实现如\coderef{code:maxSteelPriceError}
\begin{listing}[!htbp]
	\caption{钢材的最大价格(\textcolor{red}{错误解法})}
	\cppfile[firstline=5,lastline=21]{third_party/coding/cxx/algorithm/dp/src/maxSteelPrice.cc}
	\label{code:maxSteelPriceError}
\end{listing}
至此你可能认为问题已经得到了求解，但是事实上\coderef{code:maxSteelPriceError}述解法是错误的。原因在于\textbf{你的钢材也许不会被切分为两段而是三段}。只是刚好这么几个数值上两段和多段的结果相同而已。考虑多段，我们再来回头看最大价格的计算，我们可以这么思考，我们已经知道了maxPrice[x]的结果，现在想要知道maxPrice[n](n>x)的结果。我们只需要考虑两个问题：
\begin{enumerate}
	\item n能否切分为x和另一段？
	\item 切分能否获得更大的价格？
\end{enumerate}
这里的 x 实际上是一个变量，所以这个问题从长度为n的钢材切分为m段能获得的最大价格变成了：长度为n的钢材切分为一段x获得的最大价格后能否把剩余的(n-x)卖出高价格。则$maxPrice(n) = max(p[x]+maxPrice(n-x),maxPrice(n-x)),x=1\ldots,n-1$，这时我们认为钢材的最大价格为钢材切割后，两段的价格。不过要求其中一段为长度r的最大价格。例如$maxPrice(5) = max(p[2]+maxPrice(3))=8+5=13$，最朴素实现如\coderef{code:maxSteelPriceSimple}
\begin{listing}[H]
	\caption{钢材的最大价格（简单实现）}
	\cppfile[firstline=23,lastline=34]{third_party/coding/cxx/algorithm/dp/src/maxSteelPrice.cc}
	\label{code:maxSteelPriceSimple}
\end{listing}
递归实现的问题在于重复计算。例如：计算maxPrice(4)，需要计算maxPrice(3)+p[1]、maxPrice(2)+p[2]、maxPrice(1)+p[3]、maxPrice(0)+p[4]，而计算 maxPrice(3) 同样需要计算 maxPrice(2)+p[1]、maxPrice(1)+p[2]、maxPrice(0)+p[3]。这样整个计算图如\figref{fig:maxSteelPrice}：
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{maxSteelPrice}
	\caption{钢材的最大价格递归计算}
	\label{fig:maxSteelPrice}
\end{figure}
优化算法：
\begin{itemize}
	\item 自顶向下递归计算，通常也称为带备忘录的自顶向下。
	\item 自底向上
\end{itemize}
\subsubsection*{自顶向下实现}
如果我们计算maxPrice(2)的时候因为其值没有，所以需要递归计算实现maxPrice(2)。如果maxPrice(2)计算了，那么计算 maxPrice(4) 和 maxPrice(3)的时候都能使用，自顶向下计算的优化在于保存了每个值的结果。这样就不用递归计算了，如\coderef{code:maxSteelPriceTtoD}：
\begin{listing}[!htbp]
	\caption{钢材的最大价格（递归实现）}
	\cppfile[firstline=23,lastline=34]{third_party/coding/cxx/algorithm/dp/src/maxSteelPrice.cc}
	\label{code:maxSteelPriceTtoD}
\end{listing}
\subsubsection*{自底向上}
此算法是上面算法的逆过程，我们很容易其得到 maxPrice(0)=0 求解 maxPrice(1) 的时候就可以直接用到maxPrice(0)，如果要求 maxPrice(n) 我们则需要依次计算 maxPrice(0)-maxPrice(n-1)，实现如\coderef{code:maxSteelPriceDtoT}
\begin{listing}[!htbp]
	\caption{钢材的最大价格}
	\cppfile[firstline=49,lastline=55]{third_party/coding/cxx/algorithm/dp/src/maxSteelPrice.cc}
	\label{code:maxSteelPriceDtoT}
\end{listing}
将一个大问题分解为递归的子问题，子问题有最优解，整个问题就有最优解。求解动态规划问题一般流程如下：
\begin{itemize}
	\item 状态：问题解的描述，原来问题中通过切分问题能改变的量，这个量通常是我们需要达到的目标值。例如：DP[n]表示长度为n的钢材能切分后能获得的最大价格。
	\item 转移方程：对于每一个状态，可以作出一个选择以改变当前的状态。上述例子中DP[n] = max(DP[x]-price[n-x],DP[x])。
	\item 边界条件：最基本情况下问题的解。长度为n=0，价格自然为0。
\end{itemize}
\subsection{找零钱问题}
\begin{example}[找零钱问题]
给你一个整数数组 coins 表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。你可以认为每种硬币的数量是无限的。
\end{example}
\begin{itemize}
	\item 状态：和为n的最少硬币数为f(n)。如果我们通过计算到了f(n-k)，那$f(n)=min(f(n-k)+1|k\in coins)$。
	\item 转移条件：比如这里min的操作就是选择，选择到底是通过n-k获取的最小硬币数f(n-k)+1(这个硬币)还是f(n-k)（没有k只额个硬币则+0）)，怎么选是由哪种选法决定的。
	\item 边界条件：n=0的时候无法找0,n<0的时候找不到这个值，结果为-1。
\end{itemize}
DP用来存储计算结果，DP[n]表示使用零钱凑出金额n需要的最小硬币数。例如硬币是[1,2,5]凑出11需要的最小金额数为DP[11]。DP[0]=0,DP[1]=1(一个面值为1的硬币),DP[2]=1(一个面值为2的硬币)，DP[3]=2(面值为1和2的硬币两个)。
计算面值为2的最小硬币数是：
\begin{itemize}
	\item DP[0] = 0
	\item DP[1] = 1
	\item DP[2] = min(DP[2-1]+1,DP[2-2]+1,DP[2-5]+1) 中的最小值 = 1
	\item DP[3] = min(DP[3-1]+1,DP[3-2]+1,DP[3-5]+1)中最小值 = 2
\end{itemize}
自顶向下实现\coderef{code:coinTtoD}。
\begin{listing}
	\caption{找零钱(带备忘录的自顶向下)}
	\cppfile[firstline=23,lastline=54]{third_party/coding/cxx/algorithm/dp/src/coinChange.cc}
	\label{code:coinTtoD}
\end{listing}
自底向上实现\coderef{code:coinBtoT}。
\begin{listing}
	\caption{找零钱（自底向上）}
	\cppfile[firstline=56,lastline=70]{third_party/coding/cxx/algorithm/dp/src/coinChange.cc}
	\label{code:coinBtoT}
\end{listing}
\subsection{最长公共子序列}
\begin{example}[最长公共子序列]
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
\end{example}
\begin{definition}[字符串的子序列]
	它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
\end{definition}
\begin{itemize}
	\item 状态：DP[i][j]表示输入字符串a从起点0到i（不包含i），和字符串b从起点0到j（不包含j）的最长公共字串长度。
	\item 转移方程：
	      \begin{equation}
		      DP[i][j] =
		      \begin{cases}
			      0\quad i=0\quad or\qquad j=0                  \\
			      DP[i-1][j-1]+1\quad a[i]=b[j]                 \\
			      max(DP[i-1][j],DP[i][j-1])\quad a[i]\neq b[j] \\
		      \end{cases}
	      \end{equation}
	\item 边界条件：字符串a和b的长度为0的时候结果为0。
\end{itemize}
\begin{listing}
	\caption{最长公共子序列}
	\cppfile[firstline=7,lastline=22]{third_party/coding/cxx/algorithm/dp/src/longestCommonSubsequence.cc}
	\label{code:longestCommonSubsequence}
\end{listing}
计算示意图如\figref{fig:longestCommonSubString}：
\begin{figure}
	\begin{center}
		\includegraphics[width=0.6\textwidth]{longestCommonSubString}
	\end{center}
	\caption{最长公共子串}
	\label{fig:longestCommonSubString}
\end{figure}
时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是字符串text1和text2的长度，二位数组有 m+1 行和 n+1列，所需要对 dp 中每个元素计算。空间复杂度： $O(mn)$ ，其中 m 和 n 分别是字符串 test1 和 test2 的长度，因为不包含当前数值，所以行和列分别都需要多开辟一个空间，数组长度为 $m+1$ 行和 $n+1$ 列数组。需要注意的是DP迭代中第一行和第一列如果发现a[i] = b[j]这时候有两种方案，一种是代码呈现的开区间方案，初始化部分区域后计算这两种情况可以直接DP[r][c] = DP[r-1][c-1]+1还有一种闭区间情况则DP[r][c] = 1 if a[i] == b[j] else 前一个（行或者列的前一个）。

例如其中DP[2][3]的结果表示text1中abc和text2的ac的公共子串的最长公共子串因为text1[2]==text1[1]所以最长公共子串+1。从\figref{fig:longestCommonSubString}可以看出计算DP[i][j]只和DP[i-1][j-1]、DP[i-1][j]、DP[i][j-1]有关。那么存储DP是的时候能否只存储这四个元素？
\subsection{打家劫舍}
\begin{example}[打家劫舍]
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
\end{example}
\begin{Textcode}
	输入：[1,2,3,1]
	输出：4
	解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
	偷窃到的最高金额 = 1 + 3 = 4 。
	示例 2：

	输入：[2,7,9,3,1]
	输出：12
	解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
	偷窃到的最高金额 = 2 + 9 + 1 = 12 。
\end{Textcode}
\begin{itemize}
	\item 状态：DP[i]表示从索引索引为0到i-1能偷窃到的最高金额。
	\item 转移方程：
	      \begin{equation}
		      DP[i] = max(DP[i-1],DP[i-2]+value[i-1])
	      \end{equation}
	\item 边界条件：DP[0]=0,DP[1]=value[0]。
\end{itemize}
\coderef{code:robRec}递归实现（\textcolor{red}{递归实现通常会超时，这里列出来是为了展示其想法}）：
\begin{listing}
	\caption{打家劫舍}
	\cppfile[firstline=5,lastline=19]{third_party/coding/cxx/algorithm/dp/src/rob.cc}
	\label{code:robRec}
\end{listing}
自底向上实现：
\begin{listing}
	\caption{打家劫舍（自底向上）}
	\cppfile[firstline=21,lastline=35]{third_party/coding/cxx/algorithm/dp/src/rob.cc}
	\label{code:robBtoT}
\end{listing}
因为DP[i]的最终结果之和前两个元素相关，存储结果的时候只需要存储两个元素，这样能做到最小占用。
\subsection{最长递增子序列}
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
\begin{Textcode}
	示例 1：
	输入：nums = [10,9,2,5,3,7,101,18]
	输出：4
	解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
	示例 2：
	输入：nums = [0,1,0,3,2,3]
	输出：4
	示例 3：
	输入：nums = [7,7,7,7,7,7,7]
	输出：1
\end{Textcode}
\begin{itemize}
	\item 状态：$DP[i]$表示从起点到$nums[i]$（包括）递增数组的最大长度。
	\item 转移条件：假设$DP[j]$计算出来了，需要获取$DP[i],j<i$这时候,如果$nums[i]>nums[j]$则结果为$DP[i] = max(DP[j])+1(0\leq j<i)$
	\item 边界条件：$DP[0]=1$
\end{itemize}
\begin{listing}
	\caption{最长递增子序列}
	\cppfile[firstline=6,lastline=21]{third_party/coding/cxx/algorithm/dp/src/lengthOfLIS.cc}
	\label{code:longIncString}
\end{listing}
如\figref{fig:longest_nums}，计算$DP[5]$我们需要拿着$nums[5]=7$分别和$nums[0]=10,nums[1]=9,nums[2]=2,nums[3]=5,nums[4]=3$比较、如果当前值$DP[5]$大于其之前的元素，则当前值为$DP[4]+1$。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{longest_nums}
	\caption{最长递增子序列}
	\label{fig:longest_nums}
\end{figure}
\subsection{最长回文子串}
给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
\begin{Textcode}
	输入：s = "babad"
	输出："bab"
	解释："aba" 同样是符合题意的答案。
\end{Textcode}
\begin{Mind}{最长回文子串(DP)}{}
	DP[i][j]表示字符串s[i:j]组成的字符串是回文串：那么DP[i][j] = DP[i+1][j-1] and s[i] == s[j]。值得注意的是DP[i][j] = 取决于DP[i+1][j-1]。在DP矩阵中意味着计算DP矩阵的时候应该从下往上：\figref{fig:longestPalindrome_dp}。边界条件有点特殊，DP[i][i]=True毫无疑问，我们可以在初始化的时候直接赋值。DP[i][i+1]这种情况也非常好区分，所以可以选择其作为初始条件。代码实现如\coderef{code:longestPalindromeStrDp}。
\end{Mind}
\begin{itemize}
	\item 状态：DP[i][j]表示字符串从起点到j（包括j）的字符串是否为回文字符串。
	\item 转移条件：DP[i][j] = DP[i+1][j-1] and s[i] == s[j]。
	\item 边界条件：如果s对应索引i、j有两个字符，则如果这两个字符为相同则DP[i][j] = True。
\end{itemize}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{longestPalindrome_dp}
	\caption{DP实现算法流程}
	\label{fig:longestPalindrome_dp}
\end{figure}
\begin{listing}
	\caption{最长回文串(DP)}
	\cppfile[firstline=53,lastline=80]{third_party/coding/cxx/algorithm/dp/src/longestPalindrome.cc}
	\label{code:longestPalindromeStrDp}
\end{listing}
\begin{Mind}{最长回文子串（中心扩展法）}{}
	遍历字符串中字符的每个位置，以位置作为回文中心左右扩展找到最长的回文子串。对于索引为0的位置b，分别向左右扩展。因为左边的索引已经<0，扩展结束后索引为[-1,1]，以索引0(b)扩展的左右索引为[0,0]，最大回文串长度为1。然后以0、1索引（ba）开始扩展，
	左右元素b和a不相等，索引为[1,0]此索引不合法，无疑此时最大回文子串的长度还是刚刚的1，结果为b。接着索引为1的时候左右扩展后发现b和b相等，然后扩展到不满足条件，此时最长子串为aba，ab扩展因为ab本身不相等则无法扩展。在1扩展能找到的最大回文子串为aba。如此类推。
\end{Mind}
实现：\coderef{code:longestPalindromeStr}。
\begin{listing}
	\caption{最长回文串（扩增）}
	\cppfile[firstline=23,lastline=52]{third_party/coding/cxx/algorithm/dp/src/longestPalindrome.cc}
	\label{code:longestPalindromeStr}
\end{listing}
\subsection{最长回文子序列长度}
\begin{example}[最长回文子序列长度]
	给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
	示例 1:
	输入:
	"bbbab"
	输出:

	4
	一个可能的最长回文子序列为 "bbbb"。
	示例 2:
	输入:

	"cbbd
	输出:

	2
\end{example}
\begin{Mind}{最长回文子序列长度}{}
	dp[i][j]表示字符串起点i到终点j（i和j索引均被包含）的最长回文子串长度。如果str[i]=str[j]说明以i+1到j-1的子串的长度+2就能达到dp[i][j]，如果str[i]!=str[j]，因为dp[i][j]可能由dp[i][j-1]（终点左移）得到也可能由dp[i+1][j]（起点右移），dp[i][j] = max(dp[i+1][j],dp[i][j-1])。
\end{Mind}
\begin{itemize}
	\item 状态：dp[i][j]表示从起点i到终点j的最长回文子串长度。
	\item 转移条件：如果起点元素i和终点元素j相等的话，dp[i][j]=dp[i+1][j-1]+2，否则dp[i][j] = max(dp[i][j-1],dp[i+1][j])。转移条件为max(dp[i+1][j-1]+2,dp[i+1][j-1])。这里需要特别注意的是：因为dp[1][3]需要计算dp[2][3]和dp[1][2]，所以初始化数组的时候先计算start大的值。
	\item 边界条件：dp[i][j]这里i=j时结果为1。
\end{itemize}
\begin{table}
	\centering
	\begin{tabular}{|c|c|c|c|c|c|}
		\hline
		\diagbox{start}{end} & 0 & 1 & 2                    & 3                    & 4 \\
		\hline
		0                    & 1 & 2 & 3                    & 3                    & 4 \\
		1                    & 0 & 1 & \textcolor{green}{2} & \textcolor{red}{2}   & 3 \\
		2                    & 0 & 0 & 1                    & \textcolor{green}{1} & 3 \\
		3                    & 0 & 0 & 0                    & 1                    & 1 \\
		4                    & 0 & 0 & 0                    & 0                    & 1 \\
		\hline
	\end{tabular}
	\caption{最长回文子序列 dp 计算表}
\end{table}
\begin{listing}
	\caption{最长回文子串长度}
	\cppfile[firstline=6,lastline=25]{third_party/coding/cxx/algorithm/dp/src/longestPalindromeSubseq.cc}
	\label{code:longestPalindromeSubSeq}
\end{listing}
\subsection{不同的路径}
\begin{example}[不同的路径]
一个机器人在$m\times n$大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？备注：m和n小于等于100,并保证计算结果在int范围内。
\end{example}
如果m和n有一个元素为1,那么结果将只能横向或者纵向走到终点，此时走法只有一种。这里假设dp[m][n]表示从起点走到（m、n）所有可能的步数：
\begin{itemize}
	\item 状态：dp[i][j]表示从起点i到终点j的所有可能步数。
	\item 转移条件：dp[i][j]可以通过走到位置[i-1][j]向下走和位置[i][j-1]向右走获得。转移条件为dp[i][j] = dp[i][j-1]+dp[i-1][j]。
	\item 边界条件：如果目的位置在第一行或者第一列，那么走到目标位置只能通过向右或者向下达到，可能步数为1。
\end{itemize}
\coderef{code:uniquePaths}自顶向下实现：
\begin{listing}
	\caption{不同的路径（自顶向下）}
	\cppfile[firstline=19,lastline=30]{third_party/coding/cxx/algorithm/dp/src/uniquePaths.cc}
	\label{code:uniquePaths}
\end{listing}
\coderef{code:uniquePathsBtoT}自底向上实现：
\begin{listing}
	\caption{机器人的最大路径（自底向上）}
	\cppfile[firstline=41,lastline=59]{third_party/coding/cxx/algorithm/dp/src/uniquePaths.cc}
	\label{code:uniquePathsBtoT}
\end{listing}
\begin{table}
	\centering
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		起点 & 1 & 1                    & 1                    & 1      \\
		\hline
		1  & 1 & 1                    & 1                    & 1      \\
		\hline
		1  & 2 & 3                    & \textcolor{green}{4} & 5      \\
		\hline
		1  & 2 & \textcolor{green}{5} & \textcolor{red}{9}   & 14     \\
		\hline
		1  & 3 & 8                    & 17                   & 31(终点) \\
		\hline
	\end{tabular}
\end{table}
\subsection{礼物的最大价值}
\begin{example}[礼物的最大价值]
	\begin{equation*}
		\begin{bmatrix}
			1  & 10 & 3  & 8  \\
			12 & 2  & 9  & 6  \\
			5  & 7  & 4  & 11 \\
			3  & 7  & 16 & 5
		\end{bmatrix}
	\end{equation*}
\end{example}
\begin{itemize}
	\item 状态：$dp[i][j]$表示到达$[i,j]$礼物的最大价值（grid表示上面的价值矩阵）。
	\item 转移条件：$dp[i][j]$可以通过走到位置$[i-1][j]$获得的最大价值$dp[i-1][j]$和走到位置$[i][j-1]$获得的最大价值$dp[i][j-1]$加上$grid[i][j]$获得。当然这两条路径不能都走，所以决定走那条路决定于哪个累计和更大。例如如果$dp[i][j-1]$更大，那么走$dp[i-1][j]$是没有意义的。
	\item 边界条件：如果最大价值来源于第一行，那么获得最大价值只能从位置$[i][j]$的左边达到，如果是第一列同理只能通过位置$[i][j]$的上面达到。如果只有一行一列，那么最大价值就是当前值$grid[i][j]$。
\end{itemize}
\begin{equation}
	\begin{split}
		dp(i,j)=\begin{cases}
			 & grid[i][j]\quad i=0,j=0               \\
			 & dp(i-1,j)+grid[i][j]\quad i\neq0,j=0  \\
			 & dp(i,j-1)+grid[i][j]\quad i=0,j\neq 0 \\
			 & max(f(i,j-1),f(i-1,j))+grid[i][j]     \\
		\end{cases}
	\end{split}
\end{equation}
对于上面的例子，从左上角到右下角，只能下移或者右移，求到右下角的礼物价值最大。从[0,0]位置1开始可以向下或者向右，如果向右礼物的最大和为11,如果向下礼物的最大和为13,如果上一步选择了向右，再次选择向右价值为11+3=14,以此类推可以得到一个和原始礼物矩阵同样大小的矩阵，矩阵的最大值在右下角：
\begin{equation*}
	\begin{bmatrix}
		1  & 11 & 14 & 22 \\
		13 & 15 & 24 & 30 \\
		18 & 25 & 29 & 41 \\
		21 & 32 & 48 & 53
	\end{bmatrix}
\end{equation*}
\begin{listing}
	\caption{礼物的最大价值}
	\cppfile[firstline=5,lastline=24]{third_party/coding/cxx/algorithm/dp/src/maxValue.cc}
	\label{code:maxValueOfGift}
\end{listing}
\begin{itemize}
	\item 时间复杂度为$O(m*n)$。
	\item 空间复杂度为$O(m)$，（m表示矩阵的行数，n表示矩阵的列数）
\end{itemize}
\subsection{到达网格底部的路线和最小}
\begin{Mind}{到达网格底部的线路和最小}{}
	对于位置(r,c)到达底边的线路和最大，如果已经走到了最后一行，最大值自然是最后一行所在位置，如果到了row-1行现在走到最后一行只需要找到最后一行中元素最大的位置即可。目标是从第一行开始往下走走到最后一行使得和最大。
\end{Mind}
\begin{example}[到达网格底部的线路和最大值]
	\begin{figure}
		\centering
		\includegraphics[width=0.5\textwidth]{ma_matrix}
		\caption{数值矩阵}
	\end{figure}
\end{example}

\begin{itemize}
	\item 状态：$dp[r][c]$从[r,c]出发到达底边的路径和最大。
	\item 转移条件：
	      \begin{equation*}
		      dp[r][c]=
		      \begin{cases}
			      nums[r][c]\quad r = rows \\
			      dp[r+1][c]+\max(nums[r+1][c],nums[r+1][c+1])
		      \end{cases}
	      \end{equation*}

	\item 边界条件：dp[0][] = max(nums[0][:])如果从第一行出发，则选一个值最大的位置开始即可。
\end{itemize}
找出从起点起到底部的线路使得，线路上和最大。
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{store_matrix}
	\caption{存储数值矩阵}
\end{figure}
\begin{listing}
	\caption{线路最大和（存储优化）}
	\cppfile[firstline=1,lastline=27]{third_party/coding/cxx/algorithm/common/src/maxValue.cc}
	\label{code:maxPathSumOpt}
\end{listing}
\subsection{寻找最长不重复子串}
\begin{example}[寻找最长不重复子串]
	请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'-'z'的字符。例如"arabcacfr"中，最长的不含重复字符的子字符串是"acfr",长度为4.
\end{example}
\begin{Mind}{最长不重复子串}{}
	定义函数dp[i]表示第i个字符为结尾的不包含重复字符的子串最长长度（第i个字符必须在目标字符串中出现）。我们从左到右扫描字符串中的每个字符。当我们计算以第 i 个字符为结尾的不包含重复字符的子串的最长长度dp[i]，我们已经知道了dp[i-1]。
	显然，如果第 i 个字符之前没有出现过，那么$dp[i]=dp[i-1]+1$。例如字符串"arabcacfr"中，显然dp[0]等于1。在计算dp[1]时，下标为1的字符'r'之前没有出现过，显然dp[0]等于1。在计算dp[1]时，下标为1的字符'r'之前没有出现过，因此dp[1]等于2,即dp[1]=dp[0]+1。到目前为止，最长不含重复字符的子字符串是"ar"。
	如果第i个字符之前已经出现过。我们先计算第i个字符和它上次出现在字符串中的位置的距离，并记为d，接着分两种情形分析。
	\begin{enumerate}
		\item 第一种是d小于或者等于dp[i-1],此时第i个字符上次出现在dp[i-1]对应的最长子字符串中，因此dp[i]=d。于是这也意味着在第i个字符出现两次所夹的子字符串中在没有其它重复的字符了。在前面的例子中，我们继续计算dp[2],即注意下标为2的字符'a'为结尾的不含重复字符的子字符串的最长长度。我们注意到字符'a'在之前出现过，该字符上次出现在下标为0的位置，它们之间的距离d为2.也就是字符串'a'出现在dp[1]对应的最长不含重复字符的子字符串"ar"中，此时dp[2]=d,即dp[2]=2,对应的最长不含重复字符的子字符串是"ra"。如\figref{fig:longestCommonSubString}：
		\item 第二种情形是d大于dp[i-1],此时第i个字符上次出现在dp[i-1]对应的最长子字符串之前，因此仍然有dp[i]=dp[i-1]+1。我们接下来分析以字符串"arabcacgr"最后一个字符'r'为结尾的最长不含重复字符的子字符串的长度，即求dp[8]。它以前的一个字符'f'为结尾的最长不含重复字符的子字符串是"acf"，因此dp[7]=3。我们注意到最后一个字符'r'之前在字符串"arabcacfr"中出现过，上次出现在下标为1的位置，因此两次出现的距离d等于7,大于dp[7]。这说明上一个字符'r'不再dp[7]对应的最长不含重复字符的子字符串"acf"中，此时把字符'r'拼接到'acf'的后面也不会出现重复字符。因此dp[8]=dp[7]+1,即dp[8]=4,对应的最长不含重复字符的子字符串为"acfr"。
	\end{enumerate}
\end{Mind}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.6\textwidth]{lengthOfLongestSubstring}
	\end{center}
	\caption{重复字符是否影响长度计算}
	\label{fig:lengthOfLongestSubstring}
\end{figure}
\begin{itemize}
	\item 状态：$dp[i]$表示索引为i的最长不重复子串的长度。
	\item 转移条件：如果str[i]不在i-1为索引的最长子串中，那么dp[i]=dp[i-1]+1。如果 str[i] 存在于对应子串中则需要考虑上次出现该字符串的位置是否足够远以至于不影响子串的长度。
		\begin{equation}
			dp[i] = \begin{cases}
				dp[i-1]+1 \quad ch\not\in longest\quad or\quad dp[i] \in longest\quad and\quad d>i-loc \\
				dp[i-1]
			\end{cases}
		\end{equation}
	\item 边界条件：dp[0]=1。
\end{itemize}
\begin{listing}[!htbp]
	\caption{最长不重复字串}
	\cppfile[firstline=6,lastline=34]{third_party/coding/cxx/algorithm/dp/src/lengthOfLongestSubstring.cc}
	\label{code:longestNoRepeatStr}
\end{listing}
\subsection{目标和}
\begin{example}[目标和]
	给定一个非负整数数组，$a_1, a_2, \ldots, a_n$, 和一个目标数S。现在你有两个符号 + 和 - 。对于数组中的任意一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
	示例：
	\begin{Textcode}
		输入：nums: [1, 1, 1, 1, 1], S: 3
		输出：5
		解释：

		-1+1+1+1+1 = 3
		+1-1+1+1+1 = 3
		+1+1-1+1+1 = 3
		+1+1+1-1+1 = 3
		+1+1+1+1-1 = 3

		一共有5种方法让最终目标和为3。
	\end{Textcode}
\end{example}
我们用 dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
\begin{equation*}
	dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
\end{equation*}
该公式的含义为：我们想通过nums数组的前i个元素的和组成j，我们假设前i-1个数已经确定，通过+nums[i]或者-nums[i]求和，也可以写成递推的形式：
\begin{itemize}
	\item 状态：$dp[i][j]$表示索引为i达到目标和j的最大组合数。
	\item 转移条件：
	      \begin{equation}
		      dp[i][j] = dp[i-1][j-num[i]]+dp[i-1][j+num[i]]
		      \label{eq:目标和最大可能}
	      \end{equation}
	\item 边界条件：\begin{equation*}
		      \begin{cases}
			      dp[0][0] = 2 \quad nums[0]=0 \\
			      dp[0][nums[0]] = 1 \& dp[0][-nums[0]] = 1\quad nums[0]\neq 0
		      \end{cases}
	      \end{equation*}。
\end{itemize}
因为dp[i][j-num[i]]会导致j-num[i]为负数，在二维矩阵中负数无法索引，所以我们对计算的结果做一个平移，平移的值为nums中所有绝对值求和这样保证无论+、-怎样组合，最后的和都是正数。\textbf{这里需要注意}：
\begin{itemize}
	\item 如果dp[0][0]表示nums中第一个元素组合为0的可能性，如果nums[0]=0则可能性为两种，+0或者-0。
	\item 如果元素和的最大值都大于S则说明无论怎样都不可能组合成和为S得情况。
	\item j-num[i]和j+num[i]可能过存储左边界和右边解，计算的时候确保过界之后结果为0。
\end{itemize}
我们希望获取数组[2,1,1,2]组合为0的所有可能数。示意图如：\figref{fig:dp_nums_solve}，这里使用动态规划求解：
\begin{figure}[!htbp]
	\centering
	\includegraphics*[width=\textwidth]{dp_nums_solve}
	\caption{动态规划求解过程}
	\label{fig:dp_nums_solve}
\end{figure}
DP[i][j]表示nums数组索引i和其之前的所有元素通过（+、-）计算得到j的组合数。为了更好的存储数组，我们将数组下标范围[-6,6]转换到[0,12]。对于DP数组中元素DP[0][-2]（新的坐标下为DP[0][4]）只存在（0-2=-2这一种情况），所以DP[0][4]=1。
因为DP[i][j-nums[i]]+DP[i][j+nums[i]]，后续的结果均可以通过推导得到。例如DP[2][4]=DP[1][2]+DP[1][6]。
\begin{longlisting}
	\caption{动态规划求解目标和数}
	\cppfile[firstline=34,lastline=57]{third_party/coding/cxx/algorithm/dp/src/findTargetSumWays.cc}
	\label{code:findTargetSumWays}
\end{longlisting}
\coderef{code:findTargetSumWays}的实现我们可以看出计算出最后的结果实际上不用保存每一行的结果（每个i对应的j的结果），这样我们可以通过更新单行dp结果实现存储优化，如：\coderef{code:findTargetSumWaysOpt}
\begin{listing}[H]
	\caption{求解目标和数（存储优化）}
	\cppfile[firstline=12,lastline=32]{third_party/coding/cxx/algorithm/dp/src/findTargetSumWays.cc}
	\label{code:findTargetSumWaysOpt}
\end{listing}
\subsection{\href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/}{股票的买卖时机}}
\begin{example}{}
	给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票（\textbf{单次买卖}）。
	[7,1,5,3,6,4]
\end{example}
\begin{Mind}{股票的买卖时机（单次购买）}{}
	单次购买核心尽量找到股价最低的那一天然后在其后找到股价最高那一天，然后卖掉。尽量是因为你可能找到了最低股价，但是股价最高的时刻可能在这一刻之前，单次购买需要遍历股价，根据当前股价卖出收益更新最大利润。
\end{Mind}
单次股票买卖时机的最大收益实现如\coderef{code:maxProfit}
\begin{listing}[!htbp]
	\caption{股票的买卖时机}
	\cppfile[firstline=5,lastline=13]{third_party/coding/cxx/algorithm/dp/src/maxProfit.cc}
	\label{code:maxProfit}
\end{listing}

\subsection{股票的最大价值（多次买卖）}
\begin{example}[股票买卖II]
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。返回：你能获得的最大利润。
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
\end{example}
% \begin{Mind}{多次买卖条件股票最大价值}{}
% 	股票价格总是在上升区间或者下降区间。我们只需要找到上升区间的开始和结束点就可以求的当前这段时间的股票最大价值。我们找到所有上升区间的最小值和最大值，他们的价格差就是最大股票价值。判断上升区间（找到位置i的第一个元素，prices[i+1]>=prices[i]这个i就是上升的起点，下降的起点可以通过同样的方式找到。）然后累计差即可得到最终最大价值，
% \end{Mind}
% \begin{listing}[!htbp]
% 	\caption{股票的买卖时机（dp）}
% 	\cppfile[firstline=15,lastline=23]{third_party/coding/cxx/algorithm/dp/src/maxProfit.cc}
% 	\label{code:maxProfitDp}
% \end{listing}

\begin{Mind}{股票的最大价值(DP实现)}{}
	股票交易之后只存在两种情况，要么手上没有股票（已经卖光了），手上有股票（刚买，准备卖）。定义dp[i][j]为第i天交易结束后手上有j支股票时获得的最大收益。dp[i][0]收益最大取决于前一天（n-1）的状态。dp[i-1][0]（前一天也没有股票），dp[i-1][1]+prices[i]（还有价值prices[i]的股票），即dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])。dp[i][1]时，前一天可能是没有股票花费了prices[i]买了一支dp[i-1][0]-prices[i]，或者是前一天已经有股票但是没有卖dp[i-1][0]，同理最大价值为max(dp[i-1][0]-prices[i],dp[i-1][1])。最后一天（第n天）dp[n-1][0]一定比dp[n-1][1]更大，因为最后一天了买股票了没法卖，只可能 降低收益。
\end{Mind}
\begin{itemize}
	\item 状态：$dp[i][j]$表示第i天交易结束后剩余股票数j获得的最大利润。
	\item 转移条件：\begin{equation*}
		      \begin{split}
			      dp[i][0] &= max(dp[i-1][0],dp[i-1][1]+prices[i])\\
			      dp[i][1] &= max(dp[i-1][0]-prices[i-1],dp[i][j])\\
		      \end{split}
	      \end{equation*}
	\item 边界条件：dp[0][0]=0，dp[0][1]=-prices[0]。
\end{itemize}
\begin{listing}[!htbp]
	\caption{股票的最大价值（多次买卖）(DP)}
	\cppfile[firstline=31,lastline=44]{third_party/coding/cxx/algorithm/dp/src/maxProfit.cc}
	\label{code:maxProfitMulti}
\end{listing}

\begin{Mind}{股票的最大价（多次买卖）值（贪心实现）}
	第i天买第j天卖。只要保证有收益且买卖区间不重合即可。
\end{Mind}
为什么贪心算法能生效？比如1,2,3。我可以1买入然后3卖出。收益为2，同样我可以1买入2卖出，2买入3卖出。收益一样是2。也就是说我最需要当天买第二天买，累计收益就是总收益。
\begin{listing}[!htbp]
	\caption{股票的最大价值（多次买卖）（贪心）}
	\cppfile[firstline=46,lastline=52]{third_party/coding/cxx/algorithm/dp/src/maxProfit.cc}
	\label{code:maxProfitMulti}
\end{listing}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(n)。
\end{itemize}
贪心实现，每次先买的跌第二天卖掉，最后的价值最大。
\subsection{最长递增子序列}
\begin{example}[最长递增子序列]
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的），例如：
\end{example}
\begin{Textcode}
	输入
	[2,1,5,3,6,4,8,9,7]
	返回值
	[1,3,4,8,9]
	示例2
	[1,2,8,6,4]
	返回值
	[1,2,4]
\end{Textcode}
% TODO 更新代码实现
\subsection{零和一}
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
\begin{Textcode}
	示例 1：

	输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
	输出：4
	解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
	其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
\end{Textcode}
\begin{itemize}
	\item 状态：DP[i][m][n]表示输入字符串数组中从起点0到终点i的字符串中符合$num(0)\leq m$同时$num(1)
		      \leq n$的最大元素。
	\item 转移方程：
	      \begin{equation*}
		      DP[i][m][n] = max(DP[i-1][m][n],DP[i][m-num[0]][n-num[1]]+1)
	      \end{equation*}
	      其中$DP[i][m-num[0]][n-num[1]]+1$ 表示字符串被选中、然后贡献了一定的0和1。之后依然符合条件0和1的数量不超过m和n。
	\item 边界条件：字符串长度为0的时候结果为0。
\end{itemize}
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{zeros_and_ones}
	\caption{零和一计算示意图}
\end{figure}
自底向上实现：
\begin{listing}
	\caption{最大子集}
	\cppfile[firstline=37,lastline=61]{third_party/coding/cxx/algorithm/dp/src/findMaxForm.cc}
	\label{code:findMaxForm}
\end{listing}
\subsection{剪绳子}
\begin{example}{剪绳子}
	给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1且m>1），每段绳子的长度记为k[0]、k[1]、…… 、k[m]。请问$k[0]\times k[1]\times\cdots\times k[m]$可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
\end{example}
\begin{Mind}{剪绳子思路}{}
	定义函数$dp[n]$ 为把长度为n的绳子剪成若干段后各段长度的乘积的最大值。在剪第一刀的时候我们有n-1种可能选择，剪出的第一段长度为$1,2,\cdots,n-1$。因此$dp[n]=max(dp[i]\times dp[n-i])$，i表示剪绳子的位置，其中$0<i<n$。
\end{Mind}
对于不同长度的绳子经过剪断求乘积得到的结果分析如下：
\begin{enumerate}
	\item f(1)：无法剪，结果为0。
	\item f(2)：剪两端，结果为1。
	\item f(3)：剪成1和2或者3个1，结果为2。
	\item f(4)：剪成2、2或者1、3，或者1、2、1，结果为4。
\end{enumerate}
假设现在我们对绳子分成$n$份，每一份的长度为$x_i$。现在我们希望求的函数$f(x)=x_1\cdot x_2\cdots x_n$的最大值。因为有：
\begin{equation}
	\frac{x_1+x_2+\cdots+x_n}{n}\geq\sqrt[n]{x_1\cdot x_2\cdots x_n}
\end{equation}
等号成立的条件是$x_1=x_2=\cdots=x_n$。即$\sqrt[n]{x_1\cdot x_2\cdots x_n}$x项获得最大值$\left(\frac{x_1+x_2+\cdots+x_n}{n}\right)^n$，需要保证$\sqrt[n]{x_1\cdot x_2\cdots x_n}$，这样我们假设绳子被分割成$a$段。则有$a=\frac{n}{x}$（x是每一段的长度）。这样我们需要求使得：
\begin{equation}
	f(x)  = x^{\frac{n}{x}}    \\
	f'(x) = 0\rightarrow x = e
\end{equation}
因为$x$必须为整数，所以x为2或者3。因为3离2更接近，为3是$f(x)$值更大。也就是说，长度为n的绳子，如果能平均分成3的整数倍即可得到乘积最大($n = 3\times k+r$)。如果余1，则可以拿一个长度为3的两者组合为两个长度为2的结果（$2\times2\>1\times 3$）。当余2的时候则直接返回$3^k\times2$。
\begin{listing}[!htbp]
	\caption{剪绳子}
	\cppfile[firstline=45,lastline=65]{third_party/coding/cxx/algorithm/dp/src/maxProductCutting.cc}
	\label{code:maxProductCutting}
\end{listing}
\subsection{单词拆分}
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
\begin{Textcode}
	输入: s = "leetcode", wordDict = ["leet", "code"]
	输出: true
	解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

\end{Textcode}
我们定义dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0:i−1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置
是否合法即可，因此我们可以得出如下转移方程：
\begin{itemize}
	\item 状态：dp[i]表示输入字符串数组中从起点 0 到终点 i 的能被字典中的字符串组合。
	\item 转移方程：
	      \begin{equation*}
		      dp[i] = dp[j] \&\& s[j\ldots,i]\in words(0<j\leq dp[i])
	      \end{equation*}
	\item 边界条件：dp[0]=true。
\end{itemize}
对于输入case = "leetcode"、wordDict = ["leet","code"]，上述 dp[0]=true 用来启动判断，dp值初始化为全false，起点为dp[1]表示从0-0字符串是否能被wordDict中的字符串组合，需要开启判断，设置dp[0]=true，因为l不在wordDict中所以结果为false。
\begin{longlisting}
	\caption{单词拆分}
	\cudafile[firstline=5,lastline=17]{third_party/coding/cxx/algorithm/dp/src/wordBreak.cc}
	\label{code:wordBreak}
\end{longlisting}

\subsection{最大正方形}
\begin{example}[最大正方形]
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。示例如\figref{fig:maximalSquare}。
\end{example}
\begin{Textcode}
	输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
	输出：4
\end{Textcode}
\begin{Mind}{最大正方形}{}
	dp[i,j] 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp[i][j]那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。 对于每个位置
	dp[i,j]，检查在矩阵中该位置的值：
	\begin{itemize}
		\item 如果该位置的值是 0，则 dp[i][j] = 0，因为当前位置不可能在由 1 组成的正方形中。
		\item 如果该位置的值是 1，则dp[i][j] 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加1，状态转移方程如：
		      \begin{equation*}
			      dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
			      \label{eq:maximalquare}
		      \end{equation*}
	\end{itemize}
\end{Mind}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.5\textwidth]{maximalSquare}
	\end{center}
	\caption{最大正方形}
	\label{fig:maximalSquare}
\end{figure}

\begin{itemize}
	\item 状态：dp[i][j] 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。
	\item 转移方程：
	      \begin{equation*}
		      dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
		      \label{eq:maximalquare}
	      \end{equation*}
	\item 边界条件：dp[0][0]=1(matrix[0][0]=1)。
\end{itemize}
使用变量记录下最大矩形边长，最后边长的平方就是最大正方形。代码实现\coderef{code:maximalSquare}。
\begin{listing}[!htbp]
	\caption{最大正方形面积}
	\cppfile[firstline=5,lastline=34]{third_party/coding/cxx/algorithm/dp/src/maximalSquare.cc}
	\label{code:maximalSquare}
\end{listing}
\subsection{编辑距离}
\begin{example}[编辑距离]
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。你可以对一个单词进行如下三种操作：
\end{example}
\begin{itemize}
\item 插入一个字符
\item 删除一个字符
\item 替换一个字符
\end{itemize}
示例 1：
\begin{Textcode}
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
\end{Textcode}

\begin{Mind}{编辑距离}{}
	我们比较word1的前i个字符和word2的前j个字符。如果第word1的第i个字符和word2的第j个字符相等。本质上是比较word1[0:i-1]（右边是闭区间下不再说明）和word2[0:j-1]。上述例子中horse和ros比较的时候本质上等于hor和ro比较。算法示意图如\figref{fig:minDistance}：
\begin{itemize}
	\item 如果word1的第i个字符和word2的第j个字符不相等。我们可以在word1后面添加一个字符让i+1位置和j位置的元素相等。这样就可以等价于求解word1[:i]和word2[:j-1]。
	\item 如果word1的第i个字符和word2的第j个字符不相等。我们可以删掉word1的最后一个字符，这样就可以等价于求word1[:i-1]到word2[:j]。
	\item 如果word1的第i个字符和word2的第j个字符不相等。我们可以替换word1的最后一个字符，这样就可以等价于求word1[:i-1]到word2[:j-1]。
\end{itemize}
\end{Mind}
\begin{itemize}
	\item 状态：dp[i][j]：word1[:i]表示的字串转换为word2[:j]表示的字串需要的最小步数。
	\item 转移方程：
	      \begin{equation*}
			  dp[i][j] = \begin{cases}
			  min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1 \quad word[i]\neq word2[j]\\
				  dp[i-1][j-1] \quad word[i] = word[j]
			  \end{cases}
		      \label{eq:minDistance}
	      \end{equation*}
	  \item 边界条件：dp[0][0]=0,dp[0][c] = c,dp[r][0]=r
\end{itemize}
算法实现如\coderef{code:minDistance}。
\begin{listing}[!htbp]
	\caption{编辑距离}
	\cppfile[firstline=6,lastline=39]{third_party/coding/cxx/algorithm/dp/src/minDistance.cc}
	\label{code:minDistance}
\end{listing}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{minDistance}
	\caption{编辑距离}
	\label{fig:minDistance}
\end{figure}
\subsection{背包客问题}
\subsubsection*{0-1背包问题}
	有一个容量为 C 的背包，要用这个背包装下不同重量的物品，每个物品有一定的价值$v$和重量$w$。要求背包装下的物品的价值最大。定义一个二维数组dp 存储最大价值，其中 $dp[i][j]$ 表示前 $i$ 件物品重量不超过 $j$ 的情况下能达到的最大价值。设第 $i$ 件物品重量为 $w_i$，价值为 $v_i$，根据第 $i$ 件物品是否添加到背包中，可以分两种情况讨论：
	\begin{enumerate}
		\item 第 $i$ 件物品没添加到背包（其加入导致了超过了背包容量），总体积不超过 $j$ 的前 $i$ 件物品的最大价值就是总体积不超过 $j$ 的前 $i-1$ 件物品的最大价值，$dp[i][j] = dp[i-1][j]$。
		\item 第 $i$ 件物品添加到背包中，$dp[i][j] = dp[i-1][j-w_i] + v_i$。
	\end{enumerate}
	第 $i$ 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
	\begin{equation*}
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i]+v_i)
	\end{equation*}
	\textbf{递归定义最优解的值}：	根据上述分析的最优解的结构递归地定义问题最优解。设$dp[i][w]$表示背包容量为$w$时，$i$个物品导致的最优解的总价值，得到下式：
	\begin{equation*}
		dp[i][w] =
		\begin{cases}
			0\quad i=0\ or\ w=0   \\
			dp[i-1][w]\quad w_i>w \\
			max(dp[i-1][w-w_i]+v_i,dp[i-1][w]),i>0\ and\ w_i\leq w
		\end{cases}
	\end{equation*}
	假设条件$n=5,w=17$,物品价值表如下\tabref{tab:pack01}:
	\begin{table}[!htbp]
		\centering
		\caption{物品价值和重量}
		\begin{tabular}{llllll}
			\toprule
			物品编号 & 1 & 2 & 3  & 4  & 5  \\
			\midrule
			重量w  & 3 & 4 & 7  & 8  & 9  \\
			价值v  & 4 & 5 & 10 & 11 & 13 \\
			\bottomrule
		\end{tabular}
		\label{tab:pack01}
	\end{table}
\subsubsection*{完全背包问题}
\begin{example}[完全背包问题]
给定 n 个物品，第 i 个物品的重量为 $w_i$ 价值为$v_i$ ，和一个容量为 cap 的背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值。
\end{example}
0-1背包问题和完全背包问题的差别在于：物品可以选择的次数不同。0-1即物品可以不被选择（0）或者被选择（1）。而完全背包问题，物品可以不被选择或者被选择n次。分析和0-1背包问题相同，$DP[i][w]$表示限定容量前提之下能达到的最大价值。如果第i个物品超重了，此时的最大价值依然是$DP[i-1][w]$。$DP[i][w]$还有可能从$DP[i][w-w_i]+v[i]$转移来，即：第i个物品加入之后还有$w_i$的余量，此时正好装一个i物品，价值也就是$DP[i][w-w_i]+v[i]$。
\begin{equation*}
	dp[i][w] =
	\begin{cases}
		0\quad i=0\ or\ w=0   \\
		dp[i-1][w]\quad w_i>w \\
		max(dp[i][w-w_i]+v_i,dp[i-1][w_i]),i>0\ and\ w_i\leq w
	\end{cases}
\end{equation*}
\subsubsection{零钱兑换II}
\begin{example}[零钱兑换]
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 
示例 1：

输入：amount = 5, coins = [1, 2, 5]

输出：4

解释：有四种方式可以凑成总金额：

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1
\end{example}
\begin{Mind}{零钱兑换II实现}{}
DP[n]表示使用coins能兑换出n的组合数。
\end{Mind}
以上面的例子为例如果amount=1则结果为1,amount=2则结果为2。amount=3的时候结果也为2。也就是说DP[3] = DP[2]+DP[1]这种做法并不对。原因在于DP[2]的时候有[1,1],[2]，而在DP[1]的时候有1。他们组合为3的时候有[1,1]+[1],[2]+[1],[1]+[2]三种情况。但是[2]+[1]和[1]+[2]两种情况相同，所以DP[3]结果应该是2。我们可以这么思考，如果硬币只有1，则DP[3]只有[1,1,1]一种情况，如果有1和2，那么DP[3]有两种情况。加入了一个硬币2导致了最终结果多了一个。因为此时的DP[2]多了一个选择，这样DP[3]也在原来[1,1,1]的基础上多了一个选择。代码实现\coderef{code:change}。
\begin{longlisting}
	\caption{零钱兑换II}
	\cudafile[firstline=3,lastline=13]{third_party/coding/cxx/algorithm/dp/src/change.cc}
	\label{code:change}
\end{longlisting}
本质上此问题就是一个完全背包问题，给定背包(amount)和物品(coint)。物品可以随意选取，凑出所有正好能装在背包里面的所有物品数。分析的时候可以假设如果有只有一个物品，那么装入背包(amount)能正好装满的情况有多少种？如果有多个物品则根据已经能装满的情况下看剩余的数量能否正好装满。

\subsubsection{装满石头的背包的最大数量}
现有编号从0到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
\begin{Textcode}
	输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
	输出：3
\end{Textcode}
解释：
\begin{itemize}
	\item 1 块石头放入背包 0 ，1 块石头放入背包 1 。
	\item 每个背包中的石头总数是 [2,3,4,4] 。
	\item 背包 0 、背包 1 和 背包 2 都装满石头。
	\item 总计 3 个背包装满石头，所以返回 3 。
\end{itemize}
可以证明不存在超过 3 个背包装满石头的情况。注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
\begin{Mind}{装满石头的背包的最大数量}{}
	用一个列表记录每个包还需要多少石头才能装满，然后对这个记录从小到大排序，然后用addicionalRocks减去当前需要填充的剩余量，能填满则数量加一。实现如\coderef{code:maximumBags}。
\end{Mind}
\begin{listing}[!htbp]
	\caption{装满石头的背包的最大数量}
	\cppfile[firstline=2,lastline=19]{third_party/coding/cxx/algorithm/greedy/src/maximumBags.cc}
	\label{code:maximumBags}
\end{listing}
说明：
\begin{itemize}
	\item 对于示例，计算出还需要多少才能填满的向量[1,1,0,1]。
	\item 当前可填充的数量为2，对索引1需要1个填充就满了，这是填充满了一个，能填充量变成了2-1=1。
	\item 接着填充第二个，填充完后，装满。填充量变成了1-1=0。
	\item 因为第三个包已经装满所以直接满包数+1。
\end{itemize}
\subsection{丑数}
\begin{example}[丑数]
	给定数值n输出从小到大排序的丑数n个。我们把只包含质因子 2、3 和 5 的数称作丑数。
\end{example}
\begin{Mind}{丑数}
	dp[i]表示第i个丑数，dp[1]=1。定义三个指针p2、p3、p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时三个指针的值都是1。当$2\leq i\leq n$的时候$dp[i]=min(dp[p1]\times 2,dp[p3]\times 3,dp[p5]\times 5)$，如果相等则对应的指针+1。
\end{Mind}
\begin{longlisting}
	\caption{丑数}
	\cppfile[firstline=5,lastline=23]{third_party/coding/cxx/algorithm/dp/src/nthUglyNumber.cc}
	\label{code:uglyNum}
\end{longlisting}
\subsection{正则表达式匹配}
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
\begin{itemize}
	\item '.' 匹配任意单个字符
	\item '*' 匹配零个或多个前面的那一个元素
\end{itemize}
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

\begin{example}[实现'.'和'*'的正则表达式匹配]
	当匹配字符串的下一个字符是"*"的时候，可能存在多种匹配方式。
	\begin{enumerate}
		\item 在模式字符串向后移动两个字符，相当于*前面的内容和*一起忽略。
		\item 如果模式字符串中的第一个字符和字符串中的第一个字符匹配，则在字符串上向后移动一个字符，但是对于模式可以：
		      \begin{enumerate}
			      \item 在模式上向后移动两个字符。
			      \item 在模式上保持不变。
		      \end{enumerate}
	\end{enumerate}
\end{example}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{re_code}
	\caption{正则表达式匹配过程}
\end{figure}
TODO: 重构正则匹配
%\cppfile[firstline=1,lastline=30]{code/offer/ex26/main.cpp}
\begin{Mind}{正则匹配的动态规划实现}{}
	dp[i][j]表示字符串s的前i个字符和匹配字符串p的前j个字符是否匹配。如果是没有通配符可以得出转移方程：
	\begin{equation*}
		dp[i][j]=\begin{cases}
			dp[i-1][j-1]\quad s[i]=p[j] \\
			false\quad s[i]\neq p[j]
		\end{cases}
		\label{eq:AccMatch}
	\end{equation*}
	如果包含通配符\textcolor{red}{*}。它意味着其之前得到一个字符可能出现0次或者无限次。比如aabbc匹配aab*c，dp[2][2]中aab正好匹配，现在要得到dp[3][3]因为p[3]是通配符\textcolor{red}{*} ，所以dp[3][3]的结果由dp[2][3]（去掉要和通配符匹配的字符）决定或者dp[3][2]（去掉通配符）决定。转移方程如：
	\begin{equation*}
		dp[i][j]=\begin{cases}
			dp[i-1][j] \quad or\quad dp[i][j-2] \\
			dp[i][j-2]\quad 其它
		\end{cases}
	\end{equation*}
\end{Mind}

\begin{itemize}
	\item 状态：dp[i][j] 表示字符串s前i个字符（包括i）和p的前j个字符是否匹配。
	\item 转移方程：
	      \begin{equation*}
		      dp[i][j] =
		      \begin{cases}
			      dp[i-1][j-1]\quad s[i]=p[j]                                \\
			      dp[i-1][j-2] \quad p[j]=* \quad and \quad s[i] \neq p[j-1] \\
			      dp[i][j-2] \quad or \quad dp[i-1][j]\quad p[j]=*\quad and \quad s[i]=p[j-1]其它
		      \end{cases}
		      \label{eq:reMatch}
	      \end{equation*}
	\item 边界条件：dp[0][0]=true
\end{itemize}
这里着重介绍一下\textcolor{red}{*}时候的匹配。aabbc匹配aab*c：
\begin{itemize}
	\item 这里\textcolor{red}{b*}前面的b能和s匹配(s[i]=p[j-1])，若果不能，想要匹配则只能通过\textcolor{red}{*}消除前面的b实现匹配即：dp[i][j]=dp[i][j-2]。
	\item 如果\textcolor{red}{*}前面的字符为\textcolor{red}{.}，这意味着\textcolor{red}{.*}能匹配任意字符，次情形下需要保证字符串的前i-1个能匹配，因为第i个字符是无论怎样都能匹配，dp[i][j]=dp[i-1][j-1]。
	\item 如果\textcolor{red}{*}前面的字符是直接匹配的，那么\textcolor{red}{*}本身是否存在不影响匹配，即dp[i][j]=dp[i][j-1]
\end{itemize}
所以整个匹配模式：
\begin{itemize}
	\item 精确匹配下如果s[i]=p[j]或者是p[j]=\textcolor{red}{.}（其实和前一种情况一样）：dp[i][j] = d[i-1][j-1]。
	\item 如果p[j]为\textcolor{red}{*}：
	      \begin{itemize}
		      \item 如果p[i-1]
	      \end{itemize}
\end{itemize}
\begin{listing}[!htbp]
	\caption{正则表达式匹配}
	\cppfile[firstline=6,lastline=29]{third_party/coding/cxx/algorithm/dp/src/isMatch.cc}
	\label{code:isMatch}
\end{listing}
\subsection{分割等和子集}
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
\begin{Textcode}
	输入：nums = [1,5,11,5]
	输出：true
	解释：nums 可以分割成 [1, 5, 5] 和 [11]
\end{Textcode}
这里可以转为能否在重量为nums中找到和为总和一半的石头。
\begin{itemize}
	\item 状态：dp[i][j] 表示nums的前i个元素（包含第i个元素）的和是否为j。
	\item 转移方程：
	      \begin{equation*}
		      dp[i][j] =
		      \begin{cases}
			      dp[i-1][j-nums[j]]|dp[i-1][j] \quad j\geq nums[i] \\
			      dp[i-1][j]\quad j<nums[i]
		      \end{cases}
		      \label{eq:reMatch}
	      \end{equation*}
	\item 边界条件：dp[0][nums[0]]=true、dp[i][0]=true。
\end{itemize}

\begin{itemize}
	\item 如果元素和为奇数直接返回false，肯定不存在两个相等元素求和后为奇数否则设置target=sum>>1。
	\item nums元素<2直接返回false。
	\item 数组中最大元素>target则剩下元素一定小于target，范围false。
	\item 如果i为0则只有j=nums[0]的位置为true。
	\item 如果j为0意味着选择前0个元素组合为0，自然dp[i][0]=true。
\end{itemize}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.95\textwidth]{canPartition}
	\end{center}
	\caption{canPartition}
	\label{fig:canPartition}
\end{figure}

\begin{longlisting}
	\caption{分割等和子集}
	\cppfile[firstline=6,lastline=37]{third_party/coding/cxx/algorithm/dp/src/canPartition.cc}
	\label{code:canPartition}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度：$O(n\times target)$。
	\item 空间复杂度：$O(n\times target)$
\end{itemize}
通过滚动优化可以实现$O(target)$的时间复杂度。
\subsection{不同的二叉树}
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
\begin{Textcode}
	输入：n = 3
	输出：5
\end{Textcode}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.5\textwidth]{numTrees}
	\end{center}
	\caption{不同二叉树}
	\label{fig:numTrees}
\end{figure}
$G(n)$表示长度为$n$的序列能组成的二叉树的种类，$f(i,n)$表示以$i$为$n$不同长度的二叉搜索树个数($1\leq i\leq n$)。则$G(n)=\sum_{i=1}^nf(i,n)$其中$G(0)=0、G(1)=1$。其中$f(i,n)$由i左边和右边的节点数组成，则$f(i,n)=G(i)\times G(n-i)$，则$G(n)=\sum_{i=1}^nG(i)G(n-i)$。代码实现如\figref{code:numTrees}。
\begin{itemize}
	\item 时间复杂度$O(n^2)$。
	\item 空间复杂度$O(n)$。
\end{itemize}
\begin{longlisting}
	\caption{不同的二叉树}
	\cppfile[firstline=5,lastline=15]{third_party/coding/cxx/algorithm/dp/src/numTrees.cc}
	\label{code:numTrees}
\end{longlisting}

